package com.data.bobostructure.chapter1;

import com.data.bobostructure.utils.SortUtils;

import java.util.Arrays;
import java.util.HashMap;

/**
 *  插入排序的优化版本----提前终止内层循环（当找到合适的位置我就停）
 *
 */
public class InsertSort02 extends RuntimeException {
    private InsertSort02(){}

    private static void insertionSort(Comparable[] arr){
        int len = arr.length;

        for (int i=1;i<len;i++){
//            寻找元素arr[i] 合适的插入位置
            Comparable temp = arr[i];
            int j ;
            for ( j = i;j>0&&arr[j].compareTo(temp)>0;j--){

//              如果j>j-1就  往后挪一格
                arr[j] = arr[j-1];
            }
            // 到达临界条件之后，将元素插入合适的位置
            arr[j] = temp;
        }
}
    public static void sort(Comparable[] arr){
        insertionSort(arr);
    }


    public static void main(String[] args) {

        int N = 200000;

//        测试一般的数据集
        System.out.println("Test for random array, size = " + N + " , random range [0, " + N + "]");
        Integer[] arr1 = SortUtils.generateRandomArray(N, 0, N);
        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);


        SortUtils.testSort("com.data.structure.chapter1.InsertSort02","insertionSort", arr1);
        SortUtils.testSort("com.data.structure.chapter1.SelectionSort03","sort",arr2);

        System.out.println();

//        测试有序性更强的数据

        System.out.println("Test for more order array, size = " + N + " , random range [0, " + N + "]");
        arr1 = SortUtils.generateRandomArray(N, 0, 3);
        arr2 = Arrays.copyOf(arr1, arr1.length);


        SortUtils.testSort("com.data.structure.chapter1.InsertSort02","insertionSort", arr1);
        SortUtils.testSort("com.data.structure.chapter1.SelectionSort03","sort",arr2);

        System.out.println();

//        测试近乎有序的数据
        int swapTimes = 100;
        System.out.println("Test for nearly ordered array, size = " + N + " , swap time = " + swapTimes);
        System.out.println("Test for more more order array, size = " + N + " , random range [0, " + N + "]");
        arr1 = SortUtils.generateNearlyOrderedArray(N, swapTimes);
        arr2 = Arrays.copyOf(arr1, arr1.length);


        SortUtils.testSort("com.data.structure.chapter1.InsertSort02","insertionSort", arr1);
        SortUtils.testSort("com.data.structure.chapter1.SelectionSort03","sort",arr2);

        System.out.println();



//        Integer [] arr =SortUtils.generateRandomArray(200*1000,10,10*10*2000);
//        Integer [] arr1 = Arrays.copyOf(arr,arr.length);
////        System.out.println(arr.equals(arr1));
//        SortUtils.testSort("com.data.structure.chapter1.InsertSort02","insertionSort",arr);
//        SortUtils.testSort("com.data.structure.chapter1.InsertSort01","insertionSort",arr1);


    }
}
